package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/combinations/description/
https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html
https://programmercarl.com/0077.%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96.html

 77. 组合
 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 你可以按 任何顺序 返回答案。

 示例 1：
 输入：n = 4, k = 2
 输出：
 [
   [2,4],
   [3,4],
   [2,3],
   [1,2],
   [1,3],
   [1,4],
 ]

 示例 2：
 输入：n = 1, k = 1
 输出：[[1]]
 *
 */
class leetcode_77 {
    @Test
    fun test_1() {
        val actual = combine(4, 2)
        val expect = arrayListOf(arrayListOf(1, 2), arrayListOf(1, 3), arrayListOf(1, 4), arrayListOf(2, 3), arrayListOf(2, 4), arrayListOf(3, 4))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = combine(1, 1)
        val expect = arrayListOf(arrayListOf(1))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun combine(n: Int, k: Int): List<List<Int>> {
        // 回溯法
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        backtracking(n, k, 1, ArrayList<Int>(), result)
        return result
    }

    fun backtracking(n: Int, k: Int, start: Int, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>>) {
        // 终止条件
        if (path.size == k) {
            // println("[3] path:${path.toString()}")
            val items: ArrayList<Int> = ArrayList<Int>()
            items.addAll(path)
            result.add(items)
            // println("[4] result:${result.toString()}")
            return
        }

        // 单次循环
        // for(i in start .. n){ // [1,n]
        // 剪枝：i 至多从哪里开始？
        for (i in start..(n - (k - path.size) + 1)) {
            path.add(i)
            // println("for - [1]add ${i}, path:${path.toString()}")
            // 因为元素可以不重复，start 为i+1
            backtracking(n, k, i + 1, path, result)
            path.remove(i) // 回溯
            // println("for - [2]path:${path.toString()}")
        }
    }
}